package com.lc.hot100.lc138;

import java.util.HashMap;
import java.util.Map;

public class Main {

}

class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}

class Solution {
    public Node copyRandomList(Node head) {
        Map<Node, Node> mp = new HashMap<>();
        
        Node cur = head;
        Node newHead = new Node(0);
        Node newCur = newHead;
        while(cur != null) {
        	newCur.next = new Node(cur.val);
        	newCur = newCur.next;
        	mp.put(cur, newCur);
        	cur = cur.next;
        }
        Node t = head, t2 = newHead.next;
        while (t != null && t2 != null) {
        	
        	if (t.random == null) {
        		t2.random = null;
        	} else {
        		t2.random = mp.get(t.random);
        	}

        	t = t.next;
        	t2 = t2.next;
        }
        
       
    	
    	return newHead.next;
    	
    }
}